package zuo.middleLevel_8;

/**
 * @Author: Forx
 * @Data: 2021/6/27
 * @Desc: Algorithm - zuo.middleLevel_8
 * @Version: v1.0
 */

import com.sun.org.apache.bcel.internal.generic.RET;
import tools.generRandomBuff.RandomBuff;
import zuo.baseUP1_Hash.Hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * 给定一个整数数组A,长度为n,有1<=A[i]<=n,且对于[1,n]的整数，其
 * 中部分整数会重复出现而部分不会出现。
 * 实现算法找到[1,n]中所有未出现在A中的整数。
 * 提示：尝试实现0(n)的时间复杂度和0(1)的空间复杂度（返回值不计入空间复
 * 杂度）。
 * 输入描述：
 * 一行数字，全部为整数，空格分隔
 * A0 A1 A2 A3...
 * 输出描述：
 * 一行数字，全部为整数，空格分隔RO R1 R2 R3...
 * 示例1:
 * 输入
 * 1343
 * 输出
 *
 * 力争i位置上放i+1
 *
 * */
class Tools{
    public static void swap(int[] arr,int firstIndex,int secondIndex){
        int temp = arr[firstIndex];
        arr[firstIndex] = arr[secondIndex];
        arr[secondIndex] = temp;
    }
}

class sol{
    public int[] getNoAppearNum(int[] arr){
        int[] ans = new int[arr.length];
        Arrays.fill(ans,-1);
        for (int i = 0; i < arr.length; i++) {
            int index = i;
            while (arr[index] !=index+1 && arr[arr[index]-1]!=arr[index]){
                Tools.swap(arr, arr[index]-1,index);
            }
            if(arr[arr[index]-1]==arr[index]){
                ans[arr[index]-1] = arr[index];
            }
        }
        return ans;
    }

    public boolean test(){
        int[] buff = {1,2,6,4,3,5,7};
        System.out.println(Arrays.toString(getNoAppearNum(buff)));
        return true;
    }

}

/**
 * CC里面有一个土豪很喜欢一位女直播Kiki唱歌，平时就经常给她点赞、送礼、私聊。最近CC直播平台在举行
 * 中秋之星主播唱歌比赛，假设一开始该女主播的初始人气值为start,能够晋升下一轮人气需要刚好达到end,
 * 土豪给主播增加人气的可以采取的方法有：
 * a.
 * 点赞花费x C币，人气+2
 * b.
 * 送礼花费y C币，人气*2
 * C.
 * 私聊花费z C币，人气-2
 * 其中end远大于start且都为偶数，请写一个程序帮助土豪计算一下，最少花费多少C币就能帮助该主播
 * Kiki将人气刚好达到end,从而能够晋级下一轮？
 * 输入描述：
 * 第一行输入5个数据，分别为：x y z start end,每项数据以空格分开。
 * 其中：0<x,y,z<=10000,0<start,end<=1000000
 * 输出描述：
 * 需要花费的最少C币。
 * 示例1:
 * 输入
 * 3 100 1 2 6
 * 输出
 *  6
 *
 *  end必定是偶数,如果start也是偶数的话,那就只看点赞和送礼
 *  优化1:
 *  先找一个起始解,然后在递归的过程中发现花费大于起始解就直接退出这次递归,
 *  因为再往下必定不是最优解
 *  优化2:
 *  针对特定问题找特定的边界
 *  比如这道题start一直不能小于0
 *  且无需大于end*2
 *
 * */


class dashang{
    /**
     * @param x
     * @param y
     * @param z
     * @param start
     * @param end
     * */
    public int getMinConsume(int x,int y,int z,int start,int end,int costed,int limitCost){
        if(costed > limitCost)return Integer.MAX_VALUE;
        if(start==end)return costed;
        int c1 = getMinConsume(x,y,z,start+2,end,costed+x,limitCost);
        int c2 = getMinConsume(x,y,z,start*2,end,costed+y,limitCost);
        int min = Math.min(c1,c2);
        int c3 = getMinConsume(x,y,z,start-2,end,costed+z,limitCost);
        min = Math.min(min,c3);
        return min;
    }

}

/**
 * 如数据所示，给定有限时间为10天，可以获取得最大奖励为：11700,需要的时长为：9天，参加的活动为BOFH
 * 输入描述
 * 第一行输入数据N与D,表示有N项活动，D表示给予的时长。0<N<=1000,0<D<=10000。
 * 从第二行开始到N*1行，每行描述一个活动的信息，其中第一项表示当前活动需要花费的时间t,第二项表示可以获
 * 得的奖励a,之后有N项数据，表示当前活动与其他活动的依赖关系，1表示有依赖，0表示无依赖，每项数据用空格
 * 分式：
 * 输出两项数据A与T,用空格分割。A表示所获得的最大奖励，T表示所需要的时长。
 * 输入
 * 8 10
 *        A B C D E F G H
 * 3 2000 0 1 1 0 0 0 0 0 A
 * 3 4000 0 0 0 1 1 0 0 0 B
 * 2 2500 0 0 0 1 0 0 0 0 C
 * 1 1600 0 0 0 0 1 1 1 0 D
 * 4 3800 0 0 0 0 0 0 0 1 E
 * 2 2600 0 0 0 0 0 0 0 1 F
 * 4 4000 0 0 0 0 0 0 0 1 G
 * 3 3500 0 0 0 0 0 0 0 0 H
 *
 * (竖着看H依赖于EFG,A什么都不依赖)
 *
 * 输出
 * 11700 9 B D F H
 * */
class Activity{
    public int[] getQuickMaxEarn(int[][] arr){
        HashSet<Integer> attend  = new HashSet<>();
        int[] mostOPT = new int[2];
        mostOPT[0] = Integer.MAX_VALUE;
        mostOPT[1] = Integer.MIN_VALUE;
        for (int i = 2; i < arr[0].length ; i++) {
            attend.add(i);
            int[] tempAns = process(arr,attend,0,10,0,i,9);
            if(tempAns[0]!=Integer.MAX_VALUE && tempAns[1]!=Integer.MIN_VALUE){
                if(tempAns[0] <= mostOPT[0]){
                    if( tempAns[1] > mostOPT[1]) {
                        mostOPT[0] = tempAns[0];
                        mostOPT[1] = tempAns[1];
                    }
                }
                if(tempAns[1] >= mostOPT[1]){
                    if( tempAns[0] < mostOPT[0]) {
                        mostOPT[0] = tempAns[0];
                        mostOPT[1] = tempAns[1];
                    }
                }
            }

            attend.remove(i);
        }
        return mostOPT;
    }
    private int[] process(int[][] arr, HashSet<Integer> attended,int costTime, int timeLimit,int award,int curNode,int endNode){
        if(costTime > timeLimit)return new int[]{Integer.MAX_VALUE,Integer.MIN_VALUE};
        if(curNode==endNode) return new int[]{costTime,award};
        int[] canAttend = findAttend(arr,attended);
        int[] mostOPT = new int[2];
        mostOPT[0] = Integer.MAX_VALUE;
        mostOPT[1] = Integer.MIN_VALUE;
        for (int i = 0; i < canAttend.length; i++) {
            attended.add(canAttend[i]);
            int[] tempAns = process(arr,attended,costTime+arr[canAttend[i]-2][0],timeLimit,award+arr[canAttend[i]-2][1],canAttend[i],endNode);
            if(tempAns[0]!=Integer.MAX_VALUE && tempAns[1]!=Integer.MIN_VALUE){
                if(tempAns[0] <= mostOPT[0]){
                        if( tempAns[1] > mostOPT[1]) {
                            mostOPT[0] = tempAns[0];
                            mostOPT[1] = tempAns[1];
                        }
                }
                if(tempAns[1] >= mostOPT[1]){
                    if( tempAns[0] < mostOPT[0]) {
                        mostOPT[0] = tempAns[0];
                        mostOPT[1] = tempAns[1];
                    }
                }
            }
            attended.remove(canAttend[i]);
        }
        return mostOPT;
    }
    private int[] findAttend(int[][] arr,HashSet<Integer> attended
    //        ,HashSet<Integer> tested
    ){

        int rows = arr.length;
        int cols = arr[0].length;

        ArrayList<Integer> ans  = new ArrayList<>(rows);
        for (int i = 2; i < cols; i++) {
            if(!attended.contains(i)){
                int j = 0;
                for (; j < rows; j++) {
                    if(arr[j][i] == 1 ){
                        if(attended.contains(j+2)
                        //        && !tested.contains(j+2)
                        ){
                            ans.add(i);
                            break;
                        }
                    }
                }

            }
        }
        int[] ints = new int[ans.size()];
        for (int i = 0; i < ints.length; i++) {
            ints[i] = ans.get(i);
        }
        return ints;
    }

    public void test(){
        int[][] buff = {
                { 3 ,2000 ,0 ,1 ,1, 0, 0, 0, 0, 0 },
                { 3, 4000 ,0, 0, 0, 1, 1, 0, 0, 0 },
                 {2, 2500, 0, 0, 0, 1, 0, 0, 0, 0 },
                 {1 ,1600 ,0, 0, 0, 0, 1, 1, 1, 0 },
                 {4 ,3800 ,0 ,0, 0, 0, 0, 0, 0, 1 },
                 {2 ,2600 ,0 ,0, 0, 0, 0, 0, 0, 1 },
                 {4 ,4000 ,0 ,0, 0, 0, 0, 0, 0, 1 },
                { 3 ,3500, 0 ,0, 0, 0, 0, 0, 0, 0 }
        };

        System.out.println(Arrays.toString(getQuickMaxEarn(buff)) );

    }
}
/**
 * 给定一个只由0(假）、1(真）、&(逻辑与）、|(逻辑或）和^(异或）五种字符组成
 * 的字符串express,再给定一个布尔值 desired。返回express能有多少种组合
 * 方式，可以达到desired的结果。
 * 【举例】
 * express="1^0|0|1", desired=false
 * 只有1^（(0|0)|1)和1^(0|(0|1))的组合可以得到false,返回2。
 * express="1", desired=false
 * 无组合则可以得到false,返回0
 *
 * */
class Express2Desired{
    public int getKinds(String str,char des){
        char[] chars = str.toCharArray();
        return process(chars,0,chars.length-1,des);
    }
    /**
     * @param left 数字的左边界
     * @param right 数字的右边界
     *
     *
     * */
    private int process(char[] str,int left,int right,char desired){
        if(left==right){
            return str[left]==desired?1:0;
        }
        int res = 0;
       if(desired=='1'){
           for (int i = left; i < right; i+=2) {
               if(str[i+1]=='&')
                   res+=process(str,left,i,'1') * process(str, i+2, right, '1');
               else if(str[i+1]=='|'){
                   res+=process(str,left,i,'1') * process(str, i+2, right, '1');
                   res+=process(str,left,i,'0') * process(str, i+2, right, '1');
                   res+=process(str,left,i,'1') * process(str, i+2, right, '0');
               }else {
                   res+=process(str,left,i,'0') * process(str, i+2, right, '1');
                   res+=process(str,left,i,'1') * process(str, i+2, right, '0');
               }
           }
       }else {
           for (int i = left; i < right; i+=2) {
               if(str[i+1]=='&'){
                   res+=process(str,left,i,'0') * process(str, i+2, right, '1');
                   res+=process(str,left,i,'1') * process(str, i+2, right, '0');
                   res+=process(str,left,i,'0') * process(str, i+2, right, '0');
               }
               else if(str[i+1]=='|'){
                   res+=process(str,left,i,'0') * process(str, i+2, right, '0');
               }else {
                   res+=process(str,left,i,'0') * process(str, i+2, right, '0');
                   res+=process(str,left,i,'1') * process(str, i+2, right, '1');
               }
           }
       }
       return res;

    }
    public void test(){
        System.out.println(getKinds("1^0|0|1", '0'));
    }

}
/**
 * 在一个字符串中找到没有重复字符子串中最长的长度。
 * 例如：
 * abcabcbb没有重复字符的最长子串是abc,长度为3
 * bbbbb,答案是b,长度为1
 * pwwkew,答案是wke,长度是3
 * 要求：答案必须是子串，"pwke"是一个子字符序列但不是一个子字符串。
 * */
class NoRepeatSubStr{
    public int getNoRepeatSubstrLen(String string){
        char[] chars = string.toCharArray();
        return process(chars);
    }
    private int process(char[] chars){
        int[] map = new int[256];
        Arrays.fill(map,-1);
        int len = 0;
        //...   P286
        return 0;
    }
}
/**
 * 给定一个全是小写字母的字符串str,删除多余字符，使得每种字符只保留一个，并让
 * 最终结果字符串的字典序最小
 * 【举例】
 * str="acbc",删掉第一个'c',得到"abc",是所有结果字符串中字典序最小的。
 * str="dbcacbca",删掉第一个'b'、第一个'c'、第二个'c'、第二个'a',得到"dabc",
 * 是所有结果字符串中字典序最小的。
 * */
public class ML8 {
    public static void main(String[] args) {
//        sol sol = new sol();
//        sol.test();
//        Activity activity = new Activity();
//        activity.test();
        Express2Desired express2Desired = new Express2Desired();
        express2Desired.test();
    }
}
